package 贪心;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

/**
 * @author admin
 * @version 1.0.0
 * @ClassName 检查数组对是否可以被k整除.java
 * @Description TODO
 * @createTime 2020年10月22日 14:36:00
 * 给你一个整数数组 arr 和一个整数 k ，其中数组长度是偶数，值为 n 。
 *
 * 现在需要把数组恰好分成 n / 2 对，以使每对数字的和都能够被 k 整除。
 *
 * 如果存在这样的分法，请返回 True ；否则，返回 False 。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：arr = [1,2,3,4,5,10,6,7,8,9], k = 5
 * 输出：true
 * 解释：划分后的数字对为 (1,9),(2,8),(3,7),(4,6) 以及 (5,10) 。
 * 示例 2：
 *
 * 输入：arr = [1,2,3,4,5,6], k = 7
 * 输出：true
 * 解释：划分后的数字对为 (1,6),(2,5) 以及 (3,4) 。
 * 示例 3：
 *
 *
 * 输入：arr = [-1,1,-2,2,-3,3,-4,4], k = 3
 * 输出：true
 *思路：比较余数的数量 如果可以配对 对应的余数应该是相等的
 *  int b=(a % k + k) % k; 可以把负数的余数转换成正数
 */
public class 检查数组对是否可以被k整除 {
    public static void main(String[] args) {
        class Solution {
            public boolean canArrange(int[] arr, int k) {
                HashMap<Integer,Integer> map=new HashMap<>();
                for(int a:arr){
                    int b=(a % k + k) % k;
                    map.put(b,map.getOrDefault(b,0)+1);
                }
                for(int a:map.keySet()){
                    if(a==0&&map.get(a)%2!=0){
                        return false;

                    }
                    if(a!=0&&!map.get(a).equals(map.get(k-a))){
                        return false;
                    }
                }

                return true;
            }
        }




    }
}
